package algorithm.leetcode.I1to100;


/**
 * s是长串, t是短串
 *
 * 窗口右端增加的时候,need数组和tLengthLeft是--的
 * 左端增加的时候,need数组和tLengthLeft是++的
 */

public class Q76 {

    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
        int[] need = new int[128];
        int left = 0, right = 0, size = Integer.MAX_VALUE, tLengthLeft = t.length(), start = 0;

        // 初始化need数组
        for (char c : t.toCharArray()) need[c] ++;

        // 遍历s串
        while (right < s.length()) {
            // 更新滑动窗口右侧
            char c = s.charAt(right);
            if (need[c] > 0) tLengthLeft--;
            need[c]--;

            // 如果包含所有字符,更新滑动窗口左侧
            if (tLengthLeft == 0) {
                // 这里一定是<0,表示可以右移left,若是=,右移之后不满足tLengthLeft==0了
                while (left < right && need[s.charAt(left)] < 0) {
                    need[s.charAt(left)]++;
                    left++;
                }
                // 跳出while之后肯定是need某个位置大于0,即left到right之间的子串已经不够need了
                if (size > right-left+1) {
                    size = right-left+1;
                    start = left;
                }
                need[s.charAt(left)]++;
                left++;
                tLengthLeft++;
            }
            right++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start+size);
    }

    public static void main(String[] args) {
        Q76 q76 = new Q76();
        System.out.println(q76.minWindow("bba", "ab"));
    }

}
